Welcome Homepage
Hello! I'm Tra Bui and this is my first website!
- In computational theory, a decision problem is a problem that can be answered with “yes” or “no” depending on the sets of input. One example of a decision problem would be “Is X a prime number, given x is nonnegative?”
- A decision problem is recognized as “decidable” when there are some possible algorithms that can determine the answer to that decision. On the other hand, for “undecidable” decision problems, there exists proof to show that it is impossible to construct an algorithm to categorize the answer into “yes” or “no”.
- For a decidable problem, the algorithm’s execution time will depend on the size of inputs that it has to work with. For example, back to the “Is X a prime number “ question, the larger X is, the more time it will take for the algorithm to run and determine the answer. With this idea, scientists come up with a unit called “n” which is used to calculate the size of the inputs.
- Computer scientists use the notation “Big O” to talk about the time complexity (the amount of time to execute an algorithm) or space complexity (memory size needed for the inputs).
- A problem will belong to class P if we can construct algorithms that solve it in polynomial time (P stands for “polynomial), or in computational language, O(nc) time with c is an independent constant.
- A problem is in class NP if it is easier to verify its solution rather than construct a direct algorithm to solve it (NP stands for “non-deterministic polynomial”).
- The “P versus NP” question presents an inquiry asking whether problems whose solutions can be verified (check the validity of the answer) in polynomial time can also be solved in polynomial time.
- The P versus NP problem is one of the “Millenium Prize Problems”, which remains unsolved until now. If you solve this problem, you will get 1 million $ prize.